2190-数组中紧跟 key 之后出现最频繁的数字

给你一个下标从 0 开始的整数数组 nums ，同时给你一个整数 key ，它在 nums 出现过。

**统计 **在 nums 数组中紧跟着 key 后面出现的不同整数 target 的出现次数。换言之，target
的出现次数为满足以下条件的 i 的数目：

• 0 <= i <= n - 2
• nums[i] == key 且
• nums[i + 1] == target 。

请你返回出现 最多 次数的 _ _target 。测试数据保证出现次数最多的 target 是唯一的。

示例 1：

**输入：** nums = [1,100,200,1,100], key = 1
**输出：** 100
**解释：** 对于 target = 100 ，在下标 1 和 4 处出现过 2 次，且都紧跟着 key 。
没有其他整数在 key 后面紧跟着出现，所以我们返回 100 。

示例 2：

**输入：** nums = [2,2,2,2,3], key = 2
**输出：** 2
**解释：** 对于 target = 2 ，在下标 1 ，2 和 3 处出现过 3 次，且都紧跟着 key 。
对于 target = 3 ，在下标 4 出出现过 1 次，且紧跟着 key 。
target = 2 是紧跟着 key 之后出现次数最多的数字，所以我们返回 2 。

提示：

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 测试数据保证答案是唯一的。

方法一：哈希表

思路与算法

我们不妨用 n 表示 nums 数组的元素数量。为了统计不同 target 的出现次数，我们可以用哈希表 freq 来维护。

具体而言，我们遍历 nums 数组中下标 i 在闭区间 [0, n - 2] 的元素。当 nums}[i] = \textit{key 时，nums}[i + 1] 即为 target，我们在 freq 中将该元素的出现次数加上 1。最终，我们统计哈希表 freq 中统计出现次数最多的数字，并返回作为答案。

代码

[sol1-C++]

class Solution {
public:
    int mostFrequent(vector<int>& nums, int key) {
        int n = nums.size();
        unordered_map<int, int> freq;   // 统计出现次数的哈希表
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == key) {
                ++freq[nums[i+1]];
            }
        }
        // 计算并返回最高频元素
        int maxfreq = 0;
        int res = 0;
        for (const auto& [v, f]: freq) {
            if (f > maxfreq) {
                res = v; 
                maxfreq = f;
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def mostFrequent(self, nums: List[int], key: int) -> int:
        n = len(nums)
        freq = Counter()   # 统计出现次数的哈希表
        for i in range(n - 1):
            if nums[i] == key:
                freq[nums[i+1]] += 1;
        return freq.most_common(1)[0][0]   # 计算并返回最高频元素

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums 的长度。即为统计各个 target 出现次数哈希表，并计算出现次数最多的 target 的时间复杂度。

• 空间复杂度：O(n)，即为统计各个 target 出现次数哈希表的空间开销。